#pragma once

#include <algorithm>
#include <iterator>
#include <queue>
#include <unordered_map>
#include <utility>
#include <vector>

namespace jianzhi_060
{

class Solution
{
public:
    std::vector<int> topKFrequent(std::vector<int>& nums, int k)
    {
        std::unordered_map<int, int> num_freq;
        for (auto num : nums) {
            if (!num_freq.count(num))
                num_freq[num] = 0;
            ++num_freq[num];
        }

        std::vector<std::pair<int, int>> freq_sorted{num_freq.cbegin(), num_freq.cend()};
        std::sort(freq_sorted.begin(), freq_sorted.end(),
                  [](auto& lhs, auto& rhs) { return lhs.second > rhs.second; });

        std::vector<int> top_k;
        std::transform(freq_sorted.cbegin(), freq_sorted.cbegin() + k, std::back_inserter(top_k),
                       [](auto& num_and_freq) { return num_and_freq.first; });
        return top_k;
    }

    std::vector<int> topKFrequent2(std::vector<int>& nums, int k)
    {
        std::unordered_map<int, int> num_freq;
        for (auto num : nums) {
            if (!num_freq.count(num))
                num_freq[num] = 0;
            ++num_freq[num];
        }

        using NumFreq = std::pair<int, int>;
        auto greater = [](const NumFreq& lhs, const NumFreq& rhs) {
            return lhs.second > rhs.second;
        };
        std::priority_queue<NumFreq, std::vector<NumFreq>, decltype(greater)> k_max_q(greater);
        for (const auto& num_and_freq : num_freq) {
            if (k_max_q.size() < k) {
                k_max_q.push(num_and_freq);
            } else {
                if (num_and_freq.second > k_max_q.top().second) {
                    k_max_q.pop();
                    k_max_q.push(num_and_freq);
                }
            }
        }

        std::vector<int> top_k;
        while (!k_max_q.empty()) {
            top_k.push_back(k_max_q.top().first);
            k_max_q.pop();
        }
        return top_k;
    }
};

}  /* namespace jianzhi_060 */
